package com.LeeCode;

import java.util.Arrays;

/**
 * 蜡烛之间的盘子
 */

public class Code2055 {
    public static void main(String[] args) {
        String s = "***|**|*****|**||**|*";
        int[][] queries = {{1, 17}, {5, 9}};
        System.out.println(Arrays.toString(new Code2055().platesBetweenCandles(s, queries)));
    }

    public int[] platesBetweenCandles(String s, int[][] queries) {
        int n = s.length();
        int[] ans = new int[queries.length];
        char[] chars = s.toCharArray();

        // 预处理：每个位置左边最近的蜡烛位置
        int[] leftNearest = new int[n];
        int nearest = -1;
        for (int i = 0; i < n; i++) {
            if (chars[i] == '|') {
                nearest = i;
            }
            leftNearest[i] = nearest;
        }

        // 预处理：每个位置右边最近的蜡烛位置
        int[] rightNearest = new int[n];
        nearest = -1;
        for (int i = n - 1; i >= 0; i--) {
            if (chars[i] == '|') {
                nearest = i;
            }
            rightNearest[i] = nearest;
        }

        // 预处理：盘子的前缀和
        int[] platesPrefix = new int[n + 1];
        for (int i = 0; i < n; i++) {
            platesPrefix[i + 1] = platesPrefix[i] + (chars[i] == '*' ? 1 : 0);
        }

        // 处理查询
        for (int i = 0; i < queries.length; i++) {
            int left = rightNearest[queries[i][0]];   // 查询左边界右边最近的蜡烛
            int right = leftNearest[queries[i][1]];   // 查询右边界左边最近的蜡烛

            if (left != -1 && right != -1 && left < right) {
                ans[i] = platesPrefix[right] - platesPrefix[left];
            }
        }

        return ans;
    }
}
